Locating the source that triggers a dynamical process is a fundamental butchallenging problem in complex networks, ranging from epidemic spreading insociety and on the Internet to cancer metastasis in the human body. An accuratelocalization of the source is inherently limited by our ability tosimultaneously access the information of all nodes in a large-scale complexnetwork. This thus raises two critical questions: how do we locate the sourcefrom incomplete information and can we achieve full localization of sources atany possible location from a given set of observable nodes. Here we develop atime-reversal backward spreading algorithm to locate the source of adiffusion-like process efficiently and propose a general locatabilitycondition. We test the algorithm by employing epidemic spreading and consensusdynamics as typical dynamical processes and apply it to the H1N1 pandemic inChina. We find that the sources can be precisely located in arbitrary networksinsofar as the locatability condition is assured. Our tools greatly improve ourability to locate the source of diffusion in complex networks based on limitedaccessibility of nodal information. Moreover, they have implications forcontrolling a variety of dynamical processes taking place on complex networks,such as inhibiting epidemics, slowing the spread of rumors, pollution controland environmental protection.
展开▼
